package Heap;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

public class _373_FindKPairswithSmallestSums {
    public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<int[]> res = new ArrayList<>();
        PriorityQueue<int[]> p = new PriorityQueue<>((int[] p1, int[] p2) -> p2[0] + p2[1] - p1[1] - p1[0]);
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                p.offer(new int[]{nums1[i], nums2[j]});
                if (p.size() > k) {
                    p.poll();
                }
            }
        }
        res.addAll(p);
        return res;
    }
}
